Batch 2 - Class 34, 35 - Programming Finite State Machines, Mad Veterinarian

• Complete the state diagram for the wolf-goat-cabbage problem
• Think of tic-tac-toe as a state machine. Draw the states and transitions

• Tic Tac Toe
• Two floor Elevator 
• Traffic Lights
• Combination Locks
• Pacman

• (Joke) There are three kinds of people in the world. Those who can count and those who can't
• Moscow - 58 - Stopped Clock - My clock stopped. I went to my friend's place, saw the time and waited for some time, and came back and set my clock right. How did I do it without knowing the time it took me to travel from my friends house back to mine

• A Mad Veterinarian has created three animal transmogrifying machines. Place a cat in the input bin of the first machine, press the button, and .... whirrr .... bing! Open the output bins to find four dogs and one mouse. The second machine can convert a dog into three cats and three mice, and the third machine can convert a mouse into a cat and a dog. Each machine can also operate in reverse (e.g., if you’ve got two dogs and five mice, you can convert them into a cat.) This Mad Vet has one cat.

  Can he convert it into seven mice?
• Answer: Yes (1, 2, -3, -3, -3)
• Can he convert it into a pack of dogs, with no cats or mice left over?
• Answer: No (Number of Cats plus Mice is an even/odd invariant)
• Another Mad Vet has created a two animal transmogrifying machine. Machine #1 turns one cat into one dog and one cat. Machine #2 turns one dog into two cats. This Mad Vet has one cat.

  Can he convert it into 4 cats and a dog?Answer: Yes (1,1,1,1)Can he convert it into 2 cats and 2 dogs?Answer: No (Number of cats remains even or odd, whatever it started with)Ask the class to think about what can be done, and what can't from a starting point?Ensure that the kids can think of this as a state diagramCan you see the pattern to say what is possible and what isn't?Discuss a representation as a graph on a 2D plane (along X/Y axes) - are they able to see the patterns now?

  

  Apply the two dimensional representation to the first problem above by using C+M as X-axisHow would you program a mad vet setup on Appinventor?
• What if Machine #1 above turns a cat into 2 dogs and a cat? What is possible and what isn't?

  Ask kids to think about the state diagram view, as well as a graph view

• Program the state diagram you did in class (Combination Lock or Elevator)
• Another Mad Vet has these three machines: Machine #1 turns one cat into one dog. Machine #2 turns one dog into one cat, one dog, and one mouse Machine #3 turns one mouse into one cat and one dog. This Mad Vet has one cat. 

  Can she convert it into two cats?Answer: No - Invariant is (C+D+2M) mod 3Can she convert it into three cats?Answer: No - Same as aboveCan she convert it into three cats and one dog? Answer: Yes (1, 2, 3, -1)Can she convert it into one mouse?Answer: No - Same as above The Mad Vet is looking to close down the business, but she’d like to finish his Mad Vet business owning only one mouse (and no other animals). From your answer to Question above, you know she can’t simply use the cat she has to produce one mouse. So she’ll go to the pet shop down the street and buy some animals, and then use those animals together with her one cat to produce a mouse. What animals should she buy at the pet shop? Answer: One more dogUsing these three Mad Vet machines, how many different "classes" of animals are there? Describe all of the classes. Answer: 3A friend of this Mad Vet brings her, as a birthday present, a cat and a mouse. But our Mad Vet prefers to have just one cat. Can she transmogrify her new collection of animals back to the way things were when she only had one cat? Answer: Yes - Identity notionDoes you answer to the previous question depend on the fact that our Mad Vet started with one cat? That is, if she started with ANY collection of animals, and her friend brought her a cat and a mouse, would she be able to transmogrify her collection back to the original collection? Answer: Yes - Identity notionBy adding animals from the pet shop to the cat she currently owns, is it possible for the Mad Vet to finish her Mad Vet business owning whatever collection of animals she’d like? Answer: YesDoes your answer to Question 9 above depend on the fact that she happens to currently own one cat? Answer: Yes